package tree.easy;

import tree.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 111. 二叉树的最小深度
 */
public class minDepth {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5, new TreeNode(3,new TreeNode(1), new TreeNode(6)), new TreeNode(8, new TreeNode(7), new TreeNode(9)));
        System.out.println(new minDepth().minDepth(root));
    }

    List<Integer> list = new ArrayList<>();

//    public int minDepth(TreeNode root) {
//        if (root != null) {
//            if (root.right != null) {
//                help(root.right, 1);
//            }
//            if (root.left != null) {
//                help(root.left, 1);
//            }
//            if (list.isEmpty()) {
//                return 1;
//            }
//            return Collections.min(list);
//        } else {
//            return 0;
//        }
//    }

    public void help(TreeNode root, int deep) {
        if (root != null) {
            if (root.right == null && root.left == null) {
                list.add(deep + 1);
                return;
            }
            if (root.left != null) {
                help(root.left, deep + 1);
            }
            if (root.right != null) {
                help(root.right, deep + 1);
            }
        }
    }

    /**
     * 深度优先
     *
     * @param root
     * @return
     */
//    public int minDepth(TreeNode root) {
//        if (root == null) {
//            return 0;
//        }
//        if (root.left == null && root.right == null) {
//            return 1;
//        }
//        int min_deep = Integer.MAX_VALUE;
//        if (root.left != null) {
//            min_deep = Math.min(minDepth(root.left), min_deep);
//        }
//        if (root.right != null) {
//            min_deep = Math.min(minDepth(root.right), min_deep);
//        }
//        return min_deep + 1;
//    }

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if (root.right == null || root.left == null) {
            return left + right + 1;
        } else {
            return Math.min(left, right) + 1;
        }
    }


}
